Dynamic memory allocation occurs when applications determine where to store information during runtime. Such information is stored within discrete regions of memory (typically expressed in the form “memory blocks”) the size of which is based on the data being processed and is unknown in advance. In order to allocate memory blocks during run-time, memory managers (e.g., block allocators) are used to allocate blocks of memory (i.e., discrete regions of memory) to an application upon request for activities such as sorting variables, code, or data, etc. Memory managers are also used to deallocate allocated memory blocks after the application requirements cease. After receiving a request for memory from the application, a memory manager must choose a suitable memory block and hand it over, or fail. When a block of memory is no longer needed, it may be recycled by being used for one of subsequent allocations (via, for example, a refresh operation), or by being returned to the operating system.
In some cases, memory that would otherwise be available may not be used due to a previous allocation of memory blocks. This restriction may be the result of either external or internal memory fragmentation. External memory fragmentation occurs when the largest available block of free memory is too small to hold a given object of size X, although the total amount of free memory is larger than X. Such external memory fragmentation results in space between memory blocks that contain no useful data. Internal memory fragmentation occurs when the smallest available block of free memory for an object size Y has size Z, where Z is larger than Y, and results in unused space between the last byte of a block and the first byte of a next block.
For example, with reference to FIG. 1, a conventional memory manager 100 is illustrated that consists of three blocks 110, 120, 130, each of 1024 bytes. The first two blocks 110, 120 and a part of the third block 130 are occupied, meaning that an application has already requested memory from the allocator. At the end of the third block, some free space 135 is ready for further requests. If the remainder is used up, the memory manager 100 requests further blocks from the operating system and then forwards them block by block to the application as requested.
One application that utilizes memory managers is an index server that forms part of a search engine service. In operation, the index serve creates one or more memory managers during a search call and then subsequently deletes the memory managers. At the beginning of a search call, the amount of main memory that will be required is unknown. For example, a search query may result in anywhere from zero to several thousand hits (e.g., objects), each of which requires memory allocation. Having numerous operations in parallel may result in dozens to thousands of simultaneous search calls consuming large amounts of memory (e.g., several gigabytes).
If the block size is too small, the performance of the engine in responding to the search call may be suboptimal because the memory manager allocated many blocks in succession to satisfy the search call memory requirements. Such an operation may be disadvantageous as it may result in (i) numerous memory allocation requests to the operating system; (ii) an unnecessarily large internal block list identifying the allocated blocks; and (iii) wasted memory space due to external and/or internal fragmentation. All of these factors increase processing consumption and increase the amount of time needed to process a search call, thereby resulting in increased expenses. In addition, if the index server handles many search calls in parallel and each of them wastes memory, the index server may act as a bottleneck and adversely affect overall performance.
Some conventional memory managers assign blocks that are based on the size requested by an application. However, with such arrangements, the steps involved to ultimately allocate the memory blocks can consume excessive processing power and slow task completion when there are a large number of requests.
Therefore, it should be appreciated that there remains a need for an improved method and apparatus for allocating memory blocks.